#region Licence
// Copyright (c) 2008 Tasman Logic Ltd

// Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
// and associated documentation files (the "Software"), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all copies 
// or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT 
// NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
// OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
#endregion

using System;
using System.Collections.Generic;

namespace ActiveSharp.Utils
{
    // see http://blogs.msdn.com/brada/archive/2003/04/03/49896.aspx and
    // http://msdn.microsoft.com/msdnmag/issues/05/10/MemoryModels/#S5 for comments on the safety of the low-lock approach used here

    public delegate IEnumerable<TKey> EagerLoadKeysDelegate<TKey>(TKey knownKey);
    public delegate TValue LazyLoadValueDelegate<TKey, TValue>(TKey key);

    /// <summary>
    /// A dictionary designed for lazy initialization of its contents.  
    /// Is effectively read-only, with just-in-time initialization of its contents.
    /// Intended for scenarios with lots of reads, but with the only writes being to initialise the contents.
    /// </summary>
    /// <remarks>This class is at its best when you can initialise the set keys somewhat eagerly.
    /// You don't have to initialise all the keys up front, but if you can load the keys in "batches" that 
    /// makes it more efficient. See constructor for details.</remarks>
    public class LazyDictionary<TKey, TValue> where TValue: class
    {
        /// <summary>
        /// Constructs new dictionary, complete with the delegate(s) necessary to use it
        /// </summary>
        /// <param name="getRelatedKeys">If you can eager load keys, supply this delegate.  If you cannot eager load keys, pass null for this parameter,
        /// but be aware that, in that case, building up the full set of keys becomes an order(n^2) operation (where n
        /// is the number of times that a previously unseen key is used).
        /// The delegate is called when a previously-unseen key is looked up in the dictionary. The previously unseen key
        /// is passed to the delegate.  The delegate should respond by enumerating all OTHER keys which can also be 
        /// eagerly loaded into the dictionary at this time.  (Their VALUES will still be loaded lazily, by the other delegate)
        /// You may, optionally, include the key that is passed to the delegate in the delegate's results.
        /// As an example of the intended usage, consider a dictionary keyed by <see cref="Type"/>.
        /// Whenever you do a lookup by a type that is not yet in the dictionary, this delegate will fire.  You may respond
        /// by returning an enumeration of all other types in the same assembly. I.e. as soon as we see a type from a new
        /// assembly, eagerly load _all_ the types in that assembly.
        /// </param>
        /// <param name="getValue">Gets the value that corresponds to a key.  This delegate is call for each key the 
        /// first time that key is looked up in the dictionary.  (For keys that are eager-loaded but never looked up,
        /// this delegate is never called.)  You must supply this delegate.</param>
        public LazyDictionary(
            EagerLoadKeysDelegate<TKey> getRelatedKeys,
            LazyLoadValueDelegate<TKey, TValue> getValue)
        {
            _getRelatedKeys = getRelatedKeys;
            _getValue = getValue;
        }

        EagerLoadKeysDelegate<TKey> _getRelatedKeys;
        LazyLoadValueDelegate<TKey, TValue> _getValue;
        object _dictionaryReplacementLock = new object();
        object _valueSettingLock = new object();

        // Sometimes, we replace this dictionary with an new one (containing more stuff in additional to all the stuff in the old one)
        // We do not use read locks for this, because readers will either see the complete old dictionary or the complete new one.
        Dictionary<TKey, ValueContainer> _readonlyDictionary = new Dictionary<TKey, ValueContainer>();

        /// <summary>
        /// Return the value associated with the key.  If key is not present in dictionary, it will be added automatically.
        /// </summary>
        public TValue this[TKey key]
        {
            get
            {
                ValueContainer container;
                if(!_readonlyDictionary.TryGetValue(key, out container))
                {
                    #region The dictionary doesn't contain our key, so replace it with a new dictionary that does
                    // - plus any other keys which can be eagerly loaded into the dictionary at this time.
                    // We put these extra keys in to reduce the number
                    // of trips we will make through this lock-and-copy section of the code.  
                    // While we don't use locks around the reads (because we replace the whole dictionary, which is atomic)
                    // we do use locks around the updates, just to eliminate the risk of race conditions with treads trying to simultaneously add different sets of keys (and each throwing always the other's updates)
                    #endregion
                    lock(_dictionaryReplacementLock)
                    {
                        if(!_readonlyDictionary.TryGetValue(key, out container)) // double-checked lock (safe in .NET 2.0 and later)
                        {
                            // create a new dictionary that copies all the existing stuff.  This is an order(n) operation, which is why we like to add stuff in chunks (eager loading keys) since if we add (and copy) one-by-one, the adding as a whole becomes order(n^2)
                            Dictionary<TKey, ValueContainer> newDictionary = new Dictionary<TKey, ValueContainer>(_readonlyDictionary);

                            // add new contents to it
                            container = new ValueContainer();
                            newDictionary.Add(key, container);
                            AddAdditionalKeysIfPossible(newDictionary, key);
                            
                            // replace the old dictionary with the new
                            _readonlyDictionary = newDictionary;                // atomic replacement so no locks needed for _readers_ (safe in .NET 2.0 and later for object variables with default alignment)
                        }
                    }
                }

                // get the value out of the container                
                if (container.Value == null)
                {
                    lock (_valueSettingLock)                                    // don't need to use same lock, because we are updating container (which will be in both old dictionary and new, if there is a dictionary replacement underway at the same time)
                    {
                        if (container.Value == null)                            // double checked lock (just to prevent multiple threads creating difference instances of the same value.  We don't need this lock for the dictionary's sake, since as far as it is concerned we are not mutating it)
                            container.Value = _getValue(key);                   // don't mutate the dictionary; just mutate the internal state of something it contains
                    }
                }

                return container.Value;
            }
        }

        /// <summary>
        /// Add any extra keys that can be eagerly supplied by the user-specified delegate
        /// </summary>
        void AddAdditionalKeysIfPossible(Dictionary<TKey, ValueContainer> newDictionary, TKey requestedKey)
        {
            if(_getRelatedKeys != null)
            {
                foreach (TKey key in _getRelatedKeys(requestedKey))
                {
                    if(!newDictionary.ContainsKey(key))
                        newDictionary.Add(key, new ValueContainer());  // put the key in, with an empty container for its value
                }
            }
        }

        /// <summary>
        /// A very simple wrapper around a value.  
        /// </summary>
        /// <remarks>We put <see cref="ValueContainer"/>s into the underlying dictionary.  Later, we locklessly
        /// update their Value property. That's safe because because single-value updates are atomic, and as far as 
        /// the dictionary itself is concerned, we didn't update anything (neither the key not the value, but rather something
        /// inside the vale), so we don't need to protect the dictionary with a lock while we do that.</remarks>
        private class ValueContainer
        {
            public TValue Value;
        }
    }
}
